A tendency involved in an increase in the amount of data is such that the time needed to search for data increases consistently with the amount of index of data, leading to an increased a size of a data file handled. Furthermore, there has been a demand to use larger amounts of data as an access unit in order to allow improvement of the efficiency of ECC used for hard disk drives (HDDs) or NAND flash memories.
In general, latency and the price of a memory are in a tradeoff relationship; a memory with a short latency is expensive, and an inexpensive memory has a long latency. Thus, implementing an inexpensive memory system with a short latency is difficult.
For example, memories with a short latency may be used as caches to improve the performance of the whole memory system and to minimize the use of expensive memories. However, disadvantageously, a cache miss may result in an increased latency and degraded performance, and repeating unexpected cache misses may be issued in latency sensitive applications. Furthermore, efficient use of a cache system needs the management comprising consideration of which address contents are placed in a memory with a short latency and which address contents are placed in a memory with a long latency. The cache management is performed by the policy, for example, least recently used (LRU) or using a flag whether the address has been accessed for a specified time. However, the management of the cache memory requires updating and searching for the order of addresses or the flag, which may degrade the performance.